package Leetcode;

/**
 * 一个数组，找连续和最大的子数组
 * dp记录到当前这个数的最大子数组和， 如果下个数是正的，那下个数的dp就是dp[i-1]+num[i]
 * 如果下个数是负的，那么就有用下个数和不用下个数的情况了，我从这两种情况来选一下谁最大
 * 优化的话，就不需要判断是否>0了，也就是下面的代码
 */
public class L53_MaxSubarray {
    public int maxSubArray(int[] nums) {
        int n = nums.length;

        if(n==0) return 0;

        int[] dp = new int[n];
        dp[0] = nums[0];
        for(int i=1; i < n; i++){

            //dp[i] 的确是到这个数字，目前最大的总和
            //但是，怎么从之前的结果取，就是两种了。 一种是，dp[i-1]的最大和 加上当前数字，是否和 我直接取当前数字的大，哪个大取哪个
            dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
        }

        //然后，每个数都可能是最大的，这里还需要再遍历一遍
        int max=dp[0];
        for(int i=1; i<n;i++){
            max = Math.max(max,dp[i]);
        }

        return max;
    }

    public static void main(String[] args){
        L53_MaxSubarray l = new L53_MaxSubarray();
    }
}
